package main

//#link: https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/
func main() {

}

func numWays(steps int, arrLen int) int {
	mod := int(1e9) + 7
	max := min(steps/2, arrLen-1)
	dp := make([][]int, steps+1)
	for i := range dp {
		dp[i] = make([]int, max+1)
	}
	dp[0][0] = 1
	for i := 1; i <= steps/2; i++ {
		for j := 0; j <= max; j++ {
			//原地来的
			dp[i][j] = dp[i-1][j]
			//往右一步
			if j-1 >= 0 {
				dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod
			}
			//往左一步
			if j+1 <= max {
				dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % mod
			}
		}
	}
	return dp[steps][0]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
